package leetcode.problems;

import org.junit.Test;

/**
 * Created by gmwang on 2020/2/1
 * Element Appearing More Than 25% In Sorted Array
 * 有序数组元素出现超过25%
 * 
 */
public class ElementAppearingMoreThan25InSortedArray {
    /**
     * Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.
     *
     * Return that integer.
     *
     *
     *
     * Example 1:
     *
     * Input: arr = [1,2,2,6,6,6,6,7,10]
     * Output: 6
     *
     *
     * Constraints:
     *
     * 1 <= arr.length <= 10^4
     * 0 <= arr[i] <= 10^5
     **/
    public int findSpecialInteger(int[] arr) {
//        HashMap<Integer, Integer> arrHashMap = new HashMap<>();
        int [] temp = new int[100001];
        int forth = arr.length / 4;
        for (int i = 0; i < arr.length; i++) {
            Integer de = ++ temp[arr[i]];
//            Integer de = arrHashMap.getOrDefault(arr[i], 0) + 1;
            if(de > forth){
                return arr[i];
            }
//            arrHashMap.put(arr[i],de);
        }
        return 0;
    }
    @Test
    public void test(){
        int [] nums = {1,2,2,6,6,6,6,7,10};
        int numbers = findSpecialInteger(nums);
        System.out.println(numbers);
    }
}
